package leetcode.code0174;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：2 ms, 在所有 Java 提交中击败了74.88%的用户
 *
 * 内存消耗：38.3 MB, 在所有 Java 提交中击败了14.77%的用户
 *
 * 通过测试用例：45 / 45
 *
 */
public class Solution implements IDebug {
	// 从结尾[m][n]向[0][0]出发
	public int calculateMinimumHP(int[][] dungeon) {
		int m = dungeon.length;
		int n = dungeon[0].length;
		int[][] ans = new int[m][n];
		ans[m - 1][n - 1] = minHP(1 - dungeon[m - 1][n - 1]);// 到达最后一个位置最后剩下的血量至少是1
		for (int i = m - 2; i >= 0; i--) {// 单走最后一列
			ans[i][n - 1] = minHP(ans[i + 1][n - 1] - dungeon[i][n - 1]);
		}
		for (int j = n - 2; j >= 0; j--) {// 单走最后一行
			ans[m - 1][j] = minHP(ans[m - 1][j + 1] - dungeon[m - 1][j]);
		}
		for (int i = m - 2; i >= 0; i--) {// 中间一般情况，下和右，哪个需要少，哪个备选。
			for (int j = n - 2; j >= 0; j--) {
				int cur = dungeon[i][j];
				ans[i][j] = Math.min(minHP(ans[i + 1][j] - cur), minHP(ans[i][j + 1] - cur));
			}
		}
		return ans[0][0];
	}

	private int minHP(int hp) {
		return hp <= 0 ? 1 : hp;// 血量最少也得是1
	}

	@Override
	public void debug1() {
		HelpDebug.compare(7, this.calculateMinimumHP(HelpDebug.str2array1("[[-2,-3,3],[-5,-10,1],[10,30,-5]]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(1, this.calculateMinimumHP(HelpDebug.str2array1("[[100]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
